package class1;

import common.ArrayUtils;

/**
 * 计数排序
 */
public class Code11_CountingSort {
    public static void main(String[] args) {
        int[] arr = {-1,3,-5, 5, 6, 3, 4, 5, 2, 6, 9, 0,19,1};
        ArrayUtils.printArr(arr);
        countingSort(arr);
        ArrayUtils.printArr(arr);

    }

    public static void countingSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        int max = 0, min = 0;
        for (int n : arr) {
            min = Math.min(n, min);
            max = Math.max(n, max);
        }
        int[] count = new int[max - min + 1];
        for (int num : arr) {
            count[num - min]++;
        }
        ArrayUtils.printArr(count);
        int index = 0;
        for (int i = 0; i < count.length; i++) {
            while (count[i] > 0) {
                arr[index++] = i+min;
                count[i]--;
            }
        }
    }
}
